//
// Created by win10 on 24-11-29.
//

//基于链式存储的树形数据结构
//一、二叉链式表示法

//1.结构体
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    //1.数据域
    int data;
    //左右孩子指针
    struct Ltree *lchild;
    struct Ltree *rchild;
}Ltree;

//2.创建新节点
Ltree *createLtree(int value) {
    //为子节点分配空间
    Ltree *newNode = (Ltree *) malloc(sizeof(Ltree));
    //鲁棒性判断
    if(newNode==NULL) {
        return NULL;
    }
    //值的分配
    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    return newNode;
}
//先序遍历
void preorder(Ltree *T) {
    //设置一个出口==》当我们遇到叶子节点
    if(T==NULL) {
        return;
    }
    //输出当前根节点的值==》大树拆分下去 一个个 子树 的根节点
    printf("%c",T->data);
    //设置出口
    //遍历左子树
    preorder(T->lchild);
    //遍历右子树
    preorder(T->rchild);
}
//中序遍历
void inorder(Ltree  *T) {
    //设置出口
    if(T==NULL) {
        return;
    }
    //按照优先级 先对左子树进行遍历
    inorder(T->lchild);
    //然后再打印无左子树或已经遍历左子树的节点
    printf("%c",T->data);
    //最后遍历右子树
    inorder(T->rchild);
}
//后序遍历
void lastorder(Ltree *T) {
    //设置出口
    if(T==NULL) {
        return;
    }
    //按照优先级 先对左子树遍历
    lastorder(T->lchild);
    //在对右子树遍历
    lastorder(T->rchild);
    //最后输出节点
    printf("%c",T->data);
}
//求叶子节点个数
int sum;
void getLeafNum(Ltree   *T) {
    if(T==NULL) {
        return;
    }
    //判断什么是叶子节点==》判断左右指针均为空的时候，为叶子节点
    if(T->lchild==NULL && T->rchild==NULL) {
        sum ++;
    }
    getLeafNum(T->lchild);
    getLeafNum(T->rchild);
}
//求树的高度
int depth(Ltree *T) {
    int depth=0;
    int dleft=0;
    int dright=0;
    if(T==NULL) {
        return 0;
    }
    dleft=depth(T->lchild);
    dright=depth(T->rchild);
    //取左右子树高度较高的那个加一并返回
    return dleft>dright?dleft+1:dright+1;
}

//创建树
int main(void) {
    Ltree *nodeA = createLtree('A');
    Ltree *nodeB = createLtree('B');
    Ltree *nodeD = createLtree('D');
    Ltree *nodeF = createLtree('F');
    Ltree *nodeI = createLtree('I');
    Ltree *nodeL= createLtree('L');

    //节点的连接
    nodeA->lchild = nodeB;
    nodeA->rchild = nodeD;
    nodeB->rchild = nodeD;
    nodeD->lchild = nodeI;
    nodeF->lchild = nodeL;

    //遍历
    printf("traversal beginning\n");
    preorder(nodeA);
    printf("\n");


    printf("preorder end\n");
    preorder(nodeB);
    printf("\n");

    printf("lastorder\n");
    lastorder(nodeD);
    printf("\n");

    return 0;
}
